The main goal of this paper is to develop uniformly optimal first-ordermethods for convex programming (CP). By uniform optimality we mean that thefirst-order methods themselves do not require the input of any problemparameters, but can still achieve the best possible iteration complexitybounds. By incorporating a multi-step acceleration scheme into the well-knownbundle-level method, we develop an accelerated bundle-level (ABL) method, andshow that it can achieve the optimal complexity for solving a general class ofblack-box CP problems without requiring the input of any smoothnessinformation, such as, whether the problem is smooth, nonsmooth or weaklysmooth, as well as the specific values of Lipschitz constant and smoothnesslevel. We then develop a more practical, restricted memory version of thismethod, namely the accelerated prox-level (APL) method. We investigate thegeneralization of the APL method for solving certain composite CP problems andan important class of saddle-point problems recently studied by Nesterov[Mathematical Programming, 103 (2005), pp 127-152]. We present promisingnumerical results for these new bundle-level methods applied to solve certainclasses of semidefinite programming (SDP) and stochastic programming (SP)problems.
展开▼
